1. Field of the Invention
The present invention relates to a technology for creating a sequence-pair used for a sequence-pair method serving as one method for optimizing a rectangle packing that places rectangle modules having an arbitrary size without an overlap.
2. Description of the Related Art
In VLSI layout design, the first most important design process is module placement. A design process for designating the placement of a module on the unit basis of a circuit block (hereinafter, simply referred to as a “block”) on a VLSI semiconductor chip is called a floorplan. In the floorplan, the block is arranged at a smaller region as much as possible. As a consequence, signal delay on the semiconductor chip is within a predetermined limit and the circuit can be fast. Further, the scale of VLSI can be reduced and manufacturing costs can be decreased. A two-dimensional configuration of blocks obtained by assigning a plurality of blocks without an overlap to individual positions is referred to as a block placement. The floorplan optimizes the block placement to compress the area of a convex boundary surrounding the block placement, that is, this is referred to as compaction.
A problem to give rectangle blocks with an arbitrary size and configure the blocks in the minimal rectangle boundary without the overlap of the blocks is well-known as a rectangle packing problem (“RP”). Reference character B denotes a set of N rectangle blocks (hereinafter, referred to as a “block set”) with a height and a width of a real number. The “packing” of the set B of N rectangle blocks means the block placement without the overlap of the blocks. The minimal rectangle boundary of the packing is referred to as a “chip”. Reference character RP denotes a problem for finding the packing of the set B having the minimal area of the chip. Further, the “floorplan” is defined that a chip C is divided into rectangle regions called rooms each including only one block.
The essential of the floorplan is the solution of RP. However, since the number of blocks for configuration is numerous in the VLSI layout design, the manual operation of the block placement does not necessarily obtain the optimal configuration and it further takes a long time. Therefore, a CAD device for performing the floorplan of the VLSI layout design requires an algorithm for efficient solution of RP.
The RP is well-known as NP-hard. Further, since the height and width of the block have continuous real numbers, the RP is not a simple combination optimizing problem. Therefore, in the case of the solution of RP, an iterative approach such as combinational search is employed.
In the combinational search, a solution space serving as a set of codes for prescribing a structure is defined. When there is a packing for one code in the solution space, the code is feasible. The feasible code is evaluated by the chip area of the packing corresponding to the code. In the combinational search, the feasible code having the best-evaluated packing is searched.
By searching for all codes with the combinational search, the optimal packing can be obtained. However, when there are a large number of blocks, the search range is extremely large and is not practical. Therefore, a heuristic search method is used. In the case of using the heuristic search method, in order to execute the effective search, it is important which solution space is selected. The effective search needs the solution space that is P-admissible. The P-admissible solution space satisfies the following four conditions:
(1) The solution space is finite;
(2) Every solution is feasible;
(3) Evaluation for each code is possible in polynomial time and so is the realization of the corresponding packing; and
(4) The packing corresponding to the best evaluated code in the space coincides with an optimal solution of RP.
As an extremely effective solution space for giving the P-admissible solution space, it is well-known that the codes are expressed by a sequence-pair of block names (refer to [Ref. 1], [Ref. 2], [Ref. 3], and [Ref. 4]). Features of the solution space are as follows:
(1) Since the codes are expressed only by the sequence pair of the block names, the number of combinations is (n!)2;
(2) Any packing can be expressed and, obviously, it is proved that even the minimal area solution can be expressed; and
(3) All sequence-pairs express the packing (including only the feasible code). Hereinbelow, a description will be given of a solution of RP using the sequence-pair with a floorplanner.
With a method using the sequence-pair (“sequence-pair method”), first, as an initial condition, a block placement (packing) before the optimization is given. A designer creates an initial layout with a CAD device or the like, and the initial block placement is given by rectangle approximation of a circuit device or wiring in the initial layout. Further, the floorplanner first extracts the sequence-pair from the given initial block placement. Subsequently, the floorplanner sets the extracted initial sequence-pair as an initial state, and performs the combinational search with the heuristic search method (e.g., Simulated Annealing method) to search for the optimal sequence-pair. In this case, as an evaluated value for determining the optimality of the sequence-pair, the chip area corresponding to the sequence-pair is employed. Finally, the floorplanner outputs, as the optimal packing, the packing corresponding to the sequence-pair of the optimal evaluated value.
[1] Extraction of Sequence-Pair From Packing
First, a description will be given of extracting the sequence-pair from the packing (refer to [Ref. 3]).
Reference character Π denotes the packing on the chip C. As mentioned above, the floorplan means that the chip C is divided into the rooms each including only one block. The room without including one block is “empty”. A cutting-seg denotes a linear segment forming the boundary of the rooms including four sides of the chip C. FIG. 21 shows the floorplan of the packing Π having six blocks. Reference characters a to d denote the blocks and a dotted line denotes the “cutting-seg”.
In the packing Π, a pebble p is placed in the center of the room that is not empty. The pebble p is moved to the right until it reaches the cutting-seg forming one side of the room. Subsequently, when the pebble p reaches the cutting-seg, the pebble p is then moved above until it next reaches the cutting-segs crossing like a T-shape above the cutting-seg. Subsequently, when the pebble p reaches the cutting-seg, the pebble p is moved in the right direction until it next reaches the cutting-segs crossing like a T-shape on the right side of the cutting seg. Hereinafter, similarly, the pebble p is moved above, to the right, and above, . . . until the pebble p reaches the upper right corner. The above-obtained locus of the pebble p is called “right-up locus”. Similarly, “up-left locus”, “left-down locus”, and “down-right locus” are defined. FIG. 22 shows a right-up locus, up-left locus, left-down locus, and down-right locus for a block b in the packing Π shown in FIG. 21. Hereinbelow, the right-up locus, up-left locus, left-down locus, and down-right locus for a block x are defined as RU(x), UL(x), LD(x), and DR(x).
The sum of the left-down locus and the right-up locus for the block x is referred to as a “positive locus”. Further, the sum of the up-left locus and the down-right locus for the block x is referred to as a “negative locus”. If the packing Π is given, one positive locus and one negative locus for one block are uniquely determined. Therefore, hereinlater, the positive locus and negative locus are referred to by using the block name. FIG. 23A is a diagram showing the positive locus and FIG. 23B is a diagram showing the negative locus in the packing Π shown in FIG. 21.
In this case, the establishment of the following theorems can be proved:
(Theorem 1)
No pair of positive loci cross each other. No pair of negative loci each other. (They may run along the same cutting-segs, but not cross each other.)                (End of Theorem 1.)        
From Theorem 1, m positive loci and m negative loci obviously have linear order relations. Then, the positive loci are ordered from the upper left to the lower right of the chip C, and the negative loci are ordered from the lower left to the upper right of the chip C. The sequences of the positive loci and the negative loci are referred to as P and M, respectively. The loci are uniquely specified by the block names. Therefore, the sequences P and M are represented as the sequences of module names. The above-obtained sequence pair (P, M) of the module names is defined as a “sequence-pair”. For example, referring to FIGS. 23A and 23B, the sequences P and M are represented as P=(abdecf) and M=(cbfade).
The above operation for making a corresponding relationship between the packing Π and the sequence-pair is referred to as “gridding”, and is referred to as Gridding(Π). Gridding(Π)=(P, M) is established.
Upon giving the sequence-pair having a corresponding relationship with the packing Π of the block set B, the following four partial sets Maa(X), Mbb(x), Mba(x), and Mab(x) of the block set B are uniquely determined with respect to two arbitrary blocks x and x′ in the block set B:
[Expression 1]Maa(x)={x′|x′ is after x in both P and M}  (1)Mbb(x)={x′|x′ is before x in both P and M}  (2)Mba(x)={x′|x′ is before x in P and after x in M}  (3)Mab(x)={x′|x′ is after x in P and before x in M}  (4)
For example, with respect to the sequence-pair (P, M)=(abdecf, cbfade) obtained from the packing shown in FIG. 21, four partial sets for the block b are Maa(b)={d, e, f}, Mbb(b)=φ, Mba(b)={a}, and Mab(b)={c}. Further, the following dual relation between the blocks is established:
[Expression 2]x′∈Maa(x)⇄x∈Mbb(x′)  (5)x′∈Mba(x)⇄x∈Mab(x′)  (6)
If the left side of the block x is on the right of the right side of the block x′, x is “right of” x′ (Let Gridding(Π)=(P, M). If x′∈Maa(x) then X′ is right of x in Π). Similarly, “left of”, “above”, and “below”relationships between two blocks are defined. In this case, the establishment of the following theorem is proved:
(Theorem 2)
Let Gridding(Π)=(P, M). If x′∈Maa(x) then x′ is right of x in Π. Similarly, if x′∈Mbb(x) then x′ is left of x. If x′∈Mab(x) then x′ is below x. If x′∈Mba(x) then x′ is above x.                (End of Theorem 2.)        
[2] Creation of Packing from Sequence-pair
If the sequence-pair is extracted, the blocks are rearranged in the sequence-pair, thereby searching for the optimal packing. As the effective search, the heuristic method such as simulated annealing is used. In this case, upon evaluating the packing obtained by rearranging the sequence-pair, the packing needs to be created from the sequence-pair. Although the method for creating the packing from the sequence-pair is described in [Ref. 3] and [Ref. 1], it will be briefly described here.
First, the following geometric constraints are derived from the sequence-pair (P, M):
(1) With respect to two arbitrary blocks x and x′, if x′∈Maa(x) then x′ should be right of x in the packing Π. If x′∈Mbb(x) then x′ should be left of x.
(2) With respect to two arbitrary blocks x and x′, if x′∈Mab(x) then x′ should be below x. If x′∈Mba(x) then x′ should be above x.
The packing Π for satisfying the geometric constraints is referred to as a (P, M) packing. [Ref. 3] proves that there are the (P, M) packings in all sequence-pairs (P, M). FIG. 24 shows the (P, M) packing corresponding to (P, M)=(abdecf, cbfade).
Next, a description will be given of a method for obtaining the packing having the minimal chip area in the (P, M) packing of the block set B. This packing is referred to as “(P, M)-optimal”. The (P, M)-optimal packing is obtained by applying a maximal length path algorithm to a directed acyclic graph having weighted contacts with O(m2)-time calculation.
First, a horizontal constraint graph GH=(V, EH, ΩH) is defined from the geometric constraint (1) of the sequence-pair (P, M) as follows:
[Expression 3]GH=(V, EH, ΩH)V=V1∪V2 V1={source s, sink t}V2={i|i one-to-one corresponds to each block xi in B}EH=E1∪E2H E1={(s,i),(i,t)|i∈V2}E2H={(i,j)∈V2×V2|j is right of i}ΩH={ω(s), ω(t)}∪{ω(i)|i∈V2}ω(s)=ω(t)=0, ω(i)=w(xi) (∀i∈V2)  (7)
where, V, V1, and V2 denote sets of vertexes, E, E1, and E2H denote sets of directed edges, and ΩH denotes a set of weights of vertex. s and t denote a source and a sink, respectively. Index i denotes a vertex of the horizontal constraint graph GH other than the source s and the sink t. ω(x) denotes a weight of a vertex x. w(xi) denotes a width of a block xi.
A vertical constraint graph GV=(V, EV, ΩV) is similarly defined on the basis of above-and-below positional relation of the geometrical constraint (2) and a height h(x) of a block x (∈B).
[Expression 4]GV=(V, EV, ΩV)V=V1∪V2 V1={source s, sink t}V2={i|i one-to-one corresponds to each block xi in B}EV=E1∪E2V E1{(s,i),(i,t)|i ∈V2}E2V={(i,j)∈V2×V2|j is above i}ΩV={ω(s), ω(t)}∪{ω(i)|i∈V2}ω(s)=ω(t)=0, ω(i)=h(xi) (∀i∈V2)  (8)
where, V, V1, and V2 denote sets of vertexes, E, E1, and E2V denote sets of directed edges, ΩV denotes a set of weights of vertexes. s and t denote a source and a sink, respectively. Index i denotes a vertex of the vertical constraint graph GV other than the source s and the sink t. ω(x) denotes a weight of a vertex x. h(xi) denotes a height of the block xi.
FIG. 25A is a horizontal constraint graph with the weight of the (P, M) packing corresponding to (P, M)=(abdecf, cbfade), and FIG. 25B is a vertical constraint graph with the weight thereof. Both the graphs do not include any directed closed paths. Further, with respect to a pair (xi, xj) of the block, a side exists in any of the graphs GH and GV and the side does not exist in both the graphs. Therefore, the x coordinate and the y coordinate of the block satisfy the constraint of the configuration and are also independently determined. As a consequence, the block placement without the overlap is obtained. The x coordinate and the y coordinate of the module xi (∈B) are determined as the sum of weights of vertexes other than the vertex i at a maximal length path (having the maximal sum of weights of vertexes on the path) between the source s and the vertex i in the graphs GH and GV. Similarly, the height and width of the chip are determined as the sums of weights of vertexes at the maximal length path between the source s and sink t in the graphs GH and GV. The width and height of the chip can be independently minimized, and the packing obtained as a result of minimization is the (P, M)-optimal packing. FIG. 26 shows an example of the block placement obtained as a consequence of calculating the maximal length path.
As mentioned above, the geometric constraint of the compaction in the conventional VLSI is basically extracted by rectangle-approximating the circuit device or wiring given as an initial layout and extracting the above-and-below and right-and-left relations of the rectangle blocks. In this case, when the blocks are overlapped, it is necessary to determine the initial sequence-pair by determining the shape of the blocks and the initial positional coordinates and extracting the above-and-below and right-and-left relations of the blocks while keeping the positional relation of the blocks on the initial layout. Depending on this determination, the wiring connection can be disconnected or the circuit performance can be greatly reduced.
Further, the layout design requires a predetermined clearance between the blocks under the design rule. Upon imposing the constraint using the design rule, the sequence-pair needs to be determined in consideration of the design rule.
Furthermore, in order to improve the circuit performance, a series of circuit devices need to be arranged on a linear line and plural circuit devices need to be symmetrically arranged in many cases. Therefore, in this case, the initial sequence-pair needs to be determined to store the constraints of the linear configuration and the symmetrical configuration of plural blocks on the initial layout.
However, with the conventional method as mentioned above, information on a specific configuration constraint between the blocks is eliminated and the above various constraints are not considered upon extracting the sequence-pair from the initial packing. Therefore, there is such a problem that the compaction for satisfying the constraint using the design rule and the constraint to improve the circuit performance is not performed.